package com.lihepeng.leecode.frequency.ArrayList;

import org.junit.Test;

import java.util.Arrays;

/**
 * 寻找第K 大
 */
public class Solution47 {
    /**
     * 方案 1 使用快速排序+二分
     * 快排1次 然后判断左边的元素个数是不是大于K如果是左边的元素再次进行快排，否则使用右边的
     * @param a
     * @param n
     * @param K
     * @return
     */
    public int findKth(int[] a, int n, int K) {
        int length = a.length;
        return quick(a,0,n-1,K);
    }

    /**
     * 方案2 使用堆排序方案实现
     * @param a
     * @param n
     * @param K
     * @return
     */
    public int findKth01(int[] a, int n, int K) {
        int heapSize= a.length;
        buildMaxHeap(a,heapSize);
        for (int i=a.length-1;i>=a.length-K+1;i--) {
            swap(a,0,i);
            --heapSize;
            adjectHeap(a,0,heapSize);
        }
        return a[0];
    }
    /**
     * 构建最大堆
     */
    public void buildMaxHeap(int []arr,int heapSize) {
        for (int i=heapSize/2;i>=0;i--){
            adjectHeap(arr,i,heapSize);
        }

    }

    /**
     * 调整堆结构
     */
    public void adjectHeap(int []arr,int i,int heapSize ) {
        int l = i*2+1;
        int r = i*2+2;
        int larget = i;
        if (l <heapSize && arr[l]>arr[larget]) {
            larget = l;
        }
        if (r <heapSize && arr[r] >arr[larget]) {
            larget = r;

        }
        if (larget!=i) {
            swap(arr,i,larget);
            adjectHeap(arr,larget,heapSize);
        }

    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


    /**
     * 该方案 牛客会超时  leetcode 不会
     * @param a
     * @param low
     * @param high
     * @param K
     * @return
     */
    public int quick(int[]a,int low,int high,int K) {
        int partion = partion(a, low, high);
        if (partion-low+1 == K) {
            return a[partion];
        }else if (partion -low +1>K){
            // 左边
            return quick(a,low,partion-1,K);

        }else {
            // 右边
            return quick(a,partion+1,high,K- (partion - low+1));
        }

    }
    public int partion(int[]a,int left,int right){
        int temp = a[left];
        while (left<right) {
            while (left < right && a[right] <=temp) {
                right --;
            }
            if (left == right) {
                break;
            }else {
                a[left] = a[right];
            }
            while (left < right && a[left] >=temp) {
                left++;
            }
            if (left == right) {
                break;
            }else {
                a[right] = a[left];
            }
        }
        a[left] = temp;
        return left;
    }

    private void quickSort(int[]a,int left,int right) {
        int low =left;
        int hight = right;

        if (left>= right) {
            return;
        }

        int provit = a[low];

        while (low < hight) {
            while (low <hight && a[hight] <provit) {
                hight--;
            }
            a[low] = a[hight];
            while (low < hight && a[low]>provit) {
                low++;
            }
            a[hight] = a[low];
        }
        a[low] = provit;
        quickSort(a,left,hight-1);
        quickSort(a,hight+1,right);
    }

    @Test
    public void quickSort() {
        int []arrs = {2,1,8,5,3};
        quickSort(arrs,0,arrs.length-1);
        System.out.println(Arrays.toString(arrs));
    }
}
